package algorithm;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {4,1,3,8,6,2,5,7};
        quickSort3(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int base = arr[left];
        int i = left;
        int j = right;
        while (i != j) {
            while (arr[j] >=base &&i<j) {
                j--;
            }
            while (arr[i] <= base &&i<j) {
                i++;
            }
            // i和j停下来了，交换位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // i和j相遇了，交换相遇位置和基准数的位置
        arr[left] = arr[j];
        arr[j] = base;
        System.out.println(Arrays.toString(arr));
        // 排左边的
        quickSort(arr, left, i - 1);
        // 排右边的
        quickSort(arr, i+1, right);
    }


    public static void quickSort2(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 定义基准数，最左边
        int base = arr[left];
        // 定义两个指针，分别指向最左边和最右边
        int i = left;
        int j = right;
        while (i != j) {
            // 右边指针向左移动，直到找到比基准数小的元素
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 左边指针向右移动，直到找到比基准数大的元素
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 两个指针不动了，交换两个元素的位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //两个指针相遇，交换相遇位置和基准元素
        arr[left] = arr[i];
        arr[i] = base;
        quickSort2(arr, left, i - 1);
        quickSort2(arr,i+1,right);
    }


    public static void quickSort3(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        // 定义一个基准数，一般是最左边
        int base = arr[left];
        // 定义左右两个指针
        int i = left;
        int j = right;
        while (i != j) {
            while (arr[j] >= base && i < j) {
                j--;
            }
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 交换两个位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 交换相遇和基准数
        arr[left] = arr[i];
        arr[i] = base;
        quickSort3(arr, left, i - 1);
        quickSort3(arr,i+1,right);
    }
}
